// 版权所有（c）2017 Go作者。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package field

import "math/bits"

// uint128将128位数字保存为两个64位分支，用于
// bits.Mul64和bits.Add64内部函数。
type uint128 struct {
	lo, hi uint64
}

// mul64返回a*b。
func mul64(a, b uint64) uint128 {
	hi, lo := bits.Mul64(a, b)
	return uint128{lo, hi}
}

// addMul64返回v+a*b。
func addMul64(v uint128, a, b uint64) uint128 {
	hi, lo := bits.Mul64(a, b)
	lo, c := bits.Add64(lo, v.lo, 0)
	hi, _ = bits.Add64(hi, v.hi, c)
	return uint128{lo, hi}
}

// shiftRightBy51返回一个>>51。假设a最多为115位。
func shiftRightBy51(a uint128) uint64 {
	return (a.hi << (64 - 51)) | (a.lo >> 51)
}

func feMulGeneric(v, a, b *Element) {
	a0 := a.l0
	a1 := a.l1
	a2 := a.l2
	a3 := a.l3
	a4 := a.l4

	b0 := b.l0
	b1 := b.l1
	b2 := b.l2
	b3 := b.l3
	b4 := b.l4

	// 肢体乘法的工作原理类似于笔和纸柱乘法，但是
	// 具有51位肢体而不是数字。
	// None
	// a4 a3 a2 a1 a0 x
	// b4 b3 b2 b1 b0=
	// ------------------------
	// a4b0 a3b0 a2b0 a1b0 a0b0+
	// a4b1 a3b1 a2b1 a1b1 a0b1+
	// a4b2 a3b2 a2b2 a1b2 a0b2+
	// a4b3 a3b3 a2b3 a1b3 a0b3+
	// a4b4 a3b4 a2b4 a1b4 a0b4=
	// ----------------------------------------------
	// r8 r7 r6 r5 r4 r3 r2 r1 r0
	// None
	// None
	// None
	// None
	// None
	// 可以同时对乘法进行归约。对于
	// 例如，我们不计算r5：只要乘法的结果
	// 属于r5，就像a1b4一样，我们把它乘以19，然后把结果加到r0。
	// None
	// a4b0 a3b0 a2b0 a1b0 a0b0+
	// a3b1 a2b1 a1b1 a0b1 19×a4b1+
	// a2b2 a1b2 a0b2 19×a4b2 19×a3b2+
	// a1b3 a0b3 19×a4b3 19×a3b3 19×a2b3+
	// a0b4 19×a4b4 19×a3b4 19×a2b4 19×a1b4=
	// --------------------------------------
	// r4 r3 r2 r1 r0
	// None
	// 最后，我们把这些柱子加在一起，形成宽而重叠的肢体。

	a1_19 := a1 * 19
	a2_19 := a2 * 19
	a3_19 := a3 * 19
	a4_19 := a4 * 19

	// r0=a0×b0+19×（a1×b4+a2×b3+a3×b2+a4×b1）
	r0 := mul64(a0, b0)
	r0 = addMul64(r0, a1_19, b4)
	r0 = addMul64(r0, a2_19, b3)
	r0 = addMul64(r0, a3_19, b2)
	r0 = addMul64(r0, a4_19, b1)

	// r1=a0×b1+a1×b0+19×（a2×b4+a3×b3+a4×b2）
	r1 := mul64(a0, b1)
	r1 = addMul64(r1, a1, b0)
	r1 = addMul64(r1, a2_19, b4)
	r1 = addMul64(r1, a3_19, b3)
	r1 = addMul64(r1, a4_19, b2)

	// r2=a0×b2+a1×b1+a2×b0+19×（a3×b4+a4×b3）
	r2 := mul64(a0, b2)
	r2 = addMul64(r2, a1, b1)
	r2 = addMul64(r2, a2, b0)
	r2 = addMul64(r2, a3_19, b4)
	r2 = addMul64(r2, a4_19, b3)

	// r3=a0×b3+a1×b2+a2×b1+a3×b0+19×a4×b4
	r3 := mul64(a0, b3)
	r3 = addMul64(r3, a1, b2)
	r3 = addMul64(r3, a2, b1)
	r3 = addMul64(r3, a3, b0)
	r3 = addMul64(r3, a4_19, b4)

	// r4=a0×b4+a1×b3+a2×b2+a3×b1+a4×b0
	r4 := mul64(a0, b4)
	r4 = addMul64(r4, a1, b3)
	r4 = addMul64(r4, a2, b2)
	r4 = addMul64(r4, a3, b1)
	r4 = addMul64(r4, a4, b0)

	// 乘法之后，我们需要减少（携带）这五个系数
	// None
	// 尊重元素不变量。
	// None
	// 总的来说，还原的效果与卡拉玛瑙相同，除了
	// 更广泛的输入：我们通过右移每个系数来进行进位
	// 51，并将其添加到其上方的肢体。顶部进位乘以19
	// 根据还原恒等式，添加到最低肢体。
	// None
	// 最大系数（r0）最多为111位，这保证了
	// 所有进位最多为111-51=60位，这适合uint64。
	// None
	// r0=a0×b0+19×（a1×b4+a2×b3+a3×b2+a4×b1）
	// None
	// None
	// None
	// r0<2
	// None
	// 此外，顶部系数（r4）最多为107位，因此c4最多为107位
	// 56位，c4*19最多为61位，这同样适用于uint64和
	// 允许我们轻松应用还原标识。
	// None
	// r4=a0×b4+a1×b3+a2×b2+a3×b1+a4×b0
	// None
	// None
	// None

	c0 := shiftRightBy51(r0)
	c1 := shiftRightBy51(r1)
	c2 := shiftRightBy51(r2)
	c3 := shiftRightBy51(r3)
	c4 := shiftRightBy51(r4)

	rr0 := r0.lo&maskLow51Bits + c4*19
	rr1 := r1.lo&maskLow51Bits + c0
	rr2 := r2.lo&maskLow51Bits + c1
	rr3 := r3.lo&maskLow51Bits + c2
	rr4 := r4.lo&maskLow51Bits + c3

	// 现在，所有系数都可以放入64位寄存器，但仍然太大，无法保存
	// 可以作为元素传递。因此，我们做最后一个携带链，
	// None
	*v = Element{rr0, rr1, rr2, rr3, rr4}
	v.carryPropagate()
}

func feSquareGeneric(v, a *Element) {
	l0 := a.l0
	l1 := a.l1
	l2 := a.l2
	l3 := a.l3
	l4 := a.l4

	// 平方运算的工作原理与上面的乘法完全相同，但这要归功于它的
	// 对称性我们可以把一些术语组合在一起。
	// None
	// l4 l3 l2 l1 l0 x
	// l4 l3 l2 l1 l0=
	// ------------------------
	// l4l0 l3l0 l2l0 L10L0L0+
	// l4l1 l3l1 l2l1 L10L1+
	// l4l2 l3l2 l2l2 l1l2 l0l2+
	// L3L3L3L2L3L3L0L3+
	// L4L3L4L2L4L1L4L0L4=
	// ----------------------------------------------
	// r8 r7 r6 r5 r4 r3 r2 r1 r0
	// None
	// l4l0 l3l0 l2l0 L10L0L0+
	// l3l1 l2l1 L10L1 19×l4l1+
	// l2l2 l1l2 l0l2 19×l4l2 19×l3l2+
	// l1l3 l0l3 19×l4l3 19×L3 19×l2l3+
	// l0l4 19×L4 19×L3 19×l2l4 19×L1=
	// --------------------------------------
	// r4 r3 r2 r1 r0
	// None
	// 使用预先计算的2×19×和2×19×项，我们可以用
	// 只有三个Mul64和四个Add64，而不是五个和八个。

	l0_2 := l0 * 2
	l1_2 := l1 * 2

	l1_38 := l1 * 38
	l2_38 := l2 * 38
	l3_38 := l3 * 38

	l3_19 := l3 * 19
	l4_19 := l4 * 19

	// r0=l0×l0+19×（l1×l4+l2×l3+l3×l2+l4×l1）=l0×l0+19×2×（l1×l4+l2×l3）
	r0 := mul64(l0, l0)
	r0 = addMul64(r0, l1_38, l4)
	r0 = addMul64(r0, l2_38, l3)

	// r1=l0×l1+l1×l0+19×（l2×l4+l3×l3+l4×l2）=2×l0×l1+19×2×l2×l4+19×l3×l3
	r1 := mul64(l0_2, l1)
	r1 = addMul64(r1, l2_38, l4)
	r1 = addMul64(r1, l3_19, l3)

	// r2=l0×l2+l1×l1+l2×l0+19×（l3×l4+l4×l3）=2×l0×l2+l1×l1+19×2×l3×l4
	r2 := mul64(l0_2, l2)
	r2 = addMul64(r2, l1, l1)
	r2 = addMul64(r2, l3_38, l4)

	// r3=l0×l3+l1×l2+l2×l1+l3×l0+19×l4×l4=2×l0×l3+2×l1×l2+19×l4×l4
	r3 := mul64(l0_2, l3)
	r3 = addMul64(r3, l1_2, l2)
	r3 = addMul64(r3, l4_19, l4)

	// r4=l0×l4+l1×l3+l2×l2+l3×l1+l4×l0=2×l0×l4+2×l1×l3+l2×l2
	r4 := mul64(l0_2, l4)
	r4 = addMul64(r4, l1_2, l3)
	r4 = addMul64(r4, l2, l2)

	c0 := shiftRightBy51(r0)
	c1 := shiftRightBy51(r1)
	c2 := shiftRightBy51(r2)
	c3 := shiftRightBy51(r3)
	c4 := shiftRightBy51(r4)

	rr0 := r0.lo&maskLow51Bits + c4*19
	rr1 := r1.lo&maskLow51Bits + c0
	rr2 := r2.lo&maskLow51Bits + c1
	rr3 := r3.lo&maskLow51Bits + c2
	rr4 := r4.lo&maskLow51Bits + c3

	*v = Element{rr0, rr1, rr2, rr3, rr4}
	v.carryPropagate()
}

// carryPropagate通过应用还原使肢体低于52位
// None
func (v *Element) carryPropagateGeneric() *Element {
	c0 := v.l0 >> 51
	c1 := v.l1 >> 51
	c2 := v.l2 >> 51
	c3 := v.l3 >> 51
	c4 := v.l4 >> 51

	v.l0 = v.l0&maskLow51Bits + c4*19
	v.l1 = v.l1&maskLow51Bits + c0
	v.l2 = v.l2&maskLow51Bits + c1
	v.l3 = v.l3&maskLow51Bits + c2
	v.l4 = v.l4&maskLow51Bits + c3

	return v
}
